package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-06-10 10:26
 */
public class CI503下一个更大的元素 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 1};

        int[] ints = nextGreaterElements2(nums);
        PrintUtil.print(ints);

    }


    /**
     * 1.如果是降序 则继续往后查找
     * 2.如果是升序 则可以确定前一个数字的[下一个最大元素]即是该数字,再判断该数组与前面没有[下一个最大元素]的值比较 如果大于 则该数字也是其[下一个最大元素] 否则跳过
     *
     * @param nums
     * @return
     */
    public static int[] nextGreaterElements(int[] nums) {
        int[] numsNew = new int[nums.length * 2];
        List<Integer> unDeal = new ArrayList<>();
        unDeal.add(0);

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            numsNew[i] = nums[i];
            numsNew[i + nums.length] = nums[i];
        }


        int[] bigger = new int[nums.length];
        if (numsNew[0] == max) {
            bigger[0] = -1;
        }

        for (int i = 1; i < numsNew.length; i++) {
            //遍历没有[下一个最大值]的列表 如果符合则赋值并将其移除
            Iterator<Integer> iterator = unDeal.iterator();
            while (iterator.hasNext()) {
                int index = iterator.next();
                if (numsNew[i] > numsNew[index]) {
                    bigger[index] = numsNew[i];
                    iterator.remove();
                }
            }
            if (i < nums.length) {
                //如果此值是最大值 则直接赋值为-1
                if (numsNew[i] == max) {
                    bigger[i] = -1;
                } else {
                    unDeal.add(i);
                }
            } else {
                //如果已经全部有值 则直接退出循环
                if (unDeal.size() == 0) {
                    break;
                }
            }
        }
        return bigger;
    }

    public static int[] nextGreaterElements2(int[] nums) {
        List<Integer> unDeal = new ArrayList<>();
        unDeal.add(0);

        int[] bigger = new int[nums.length];
        //默认值赋值为-1
        Arrays.fill(bigger, -1);
        for (int i = 1; i < nums.length *2 -1; i++) {
            //遍历没有[下一个最大值]的列表 如果符合则赋值并将其移除
            Iterator<Integer> iterator = unDeal.iterator();
            while (iterator.hasNext()) {
                int index = iterator.next();
                if (nums[i%nums.length] > nums[index]) {
                    bigger[index] = nums[i%nums.length];
                    iterator.remove();
                }
            }
            if (i < nums.length) {
                unDeal.add(i);
            } else {
                //如果已经全部有值 则直接退出循环
                if (unDeal.size() == 0) {
                    break;
                }
            }
        }
        return bigger;
    }

    /**
     * 栈比list更合适 原因是 list遍历的是全部  栈利用了数据波动的规律 -》未赋值的值一定是递减的!!!!
     * @param nums
     * @return
     */
    public static int[] nextGreaterElements3(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return ret;
    }



}
